package org.xi.dsaa.collection;

/**
 * 伸展树 Splay Tree
 *
 * @param <E> 元素类型
 */
public class SplayTree<E extends Comparable<E>> {

    private Node<E> root;

    public boolean exists(E item) {
        return getNode(item) != null;
    }

    public void add(E item) {
        if (root == null) {
            root = new Node<>(item);
            return;
        }
        splay(item);
        int compareResult = root.item.compareTo(item);
        if (compareResult > 0) {
            Node<E> newNode = new Node<>(item, root.left, root);
            root.left = null;
            root = newNode;
        } else if (compareResult < 0) {
            Node<E> newNode = new Node<>(item, root, root.right);
            root.right = null;
            root = newNode;
        }
    }

    public void addAll(E... items) {
        for (E item : items) {
            add(item);
        }
    }

    public void addAll(Iterable<E> items) {
        for (E item : items) {
            add(item);
        }
    }

    private Node<E> getNode(E item) {
        int compareResult;
        for (Node<E> node = root; node != null; node = compareResult > 0 ? node.left : node.right) {
            if ((compareResult = node.item.compareTo(item)) == 0) {
                return node;
            }
        }
        return null;
    }

    public void remove(E item) {
        if (root == null) {
            return;
        }
        splay(item);
        if (root.item.compareTo(item) != 0) {
            return;
        }
        if (root.left == null) {
            root = root.right;
        } else {
            Node<E> newHeader = root.left;
            newHeader = splay(item, newHeader);
            newHeader.right = root.right;
            root = newHeader;
        }
    }

    public void splay(E item) {
        root = splay(item, root);
    }

    private Node<E> splay(E item, Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> header = new Node<>(null);
        Node<E> leftMax = header, rightMin = header;
        int compareResult;
        while ((compareResult = item.compareTo(node.item)) != 0) {
            if (compareResult < 0) {
                if (node.left != null && item.compareTo(node.left.item) < 0) {
                    node = singleRotateWithLeft(node);
                }
                if (node.left == null) {
                    break;
                }
                rightMin.left = node;
                rightMin = node;
                node = node.left;
            } else {
                if (node.right != null && item.compareTo(node.right.item) > 0) {
                    node = singleRotateWithRight(node);
                }
                if (node.right == null) {
                    break;
                }
                leftMax.right = node;
                leftMax = node;
                node = node.right;
            }
        }
        leftMax.right = node.left;
        rightMin.left = node.right;
        // header 首次赋值时，左右存储相反
        node.left = header.right;
        node.right = header.left;
        return node;
    }

    private Node<E> singleRotateWithLeft(Node<E> node) {
        Node<E> tmpNode = node.left;
        node.left = tmpNode.right;
        tmpNode.right = node;
        return tmpNode;
    }

    private Node<E> singleRotateWithRight(Node<E> node) {
        Node<E> tmpNode = node.right;
        node.right = tmpNode.left;
        tmpNode.left = node;
        return tmpNode;
    }

    public static class Node<E extends Comparable<E>> {
        private E item;
        private Node<E> left;
        private Node<E> right;

        public Node(E item) {
            this(item, null, null);
        }

        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }

    public void printTree() {
        printTree(root);
    }

    private void printTree(Node<E> node) {
        if (node.left != null) {
            printTree(node.left);
        }
        System.out.println(node.item);
        if (node.right != null) {
            printTree(node.right);
        }
    }

    public static void main(String[] args) {
        SplayTree<Integer> tree = new SplayTree<>();
        tree.addAll(32, 24, 6, 3, 4, 19, 40, 9, 8, 3, 16, 10, 23, 31, 67, 18);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(24);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(8);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(8);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(17);
        tree.printTree();
    }
}
